package com.ljy.kotlindemo.leetcode

import java.util.*

/**
 * @Author: LiuJinYang
 * @CreateDate: 2021/7/15
 * @Description:
 */
internal class aaa {
    fun ab(): List<String> {
        val res = HashSet<String>()
        val m = 2
        val n = 4
        val vis = Array(m) { BooleanArray(n) }
        val D = Array(n + 1) { IntArray(m + 1) }
        return ArrayList(res)
    }

    fun countBits(n: Int): IntArray {
        val bits = IntArray(n + 1)
        var highBit = 0
        for (i in 1..n) {
            if (i and i - 1 == 0) {
                highBit = i
            }
            bits[i] = bits[i - highBit] + 1
        }
        return bits
    }

    fun totalNQueens(n: Int): Int {
        return solve(n, 0, 0, 0, 0)
    }

    fun solve(n: Int, row: Int, columns: Int, diagonals1: Int, diagonals2: Int): Int {
        return if (row == n) {
            1
        } else {
            var count = 0
            var availablePositions = (1 shl n) - 1 and (columns or diagonals1 or diagonals2).inv()
            while (availablePositions != 0) {
                val position = availablePositions and -availablePositions
                availablePositions = availablePositions and availablePositions - 1
                count += solve(
                    n,
                    row + 1,
                    columns or position,
                    diagonals1 or position shl 1,
                    diagonals2 or position shr 1
                )
            }
            count
        }
    }
}